|
In cryptography the Rabin Signature Scheme is a method of Digital signature originally proposed by Michael O. Rabin in 1979. The Rabin Signature Scheme was one of the first digital signature schemes proposed, and it was the first to relate the hardness of forgery directly to the problem of integer factorization. Because of its simplicity and prominent role in early public key cryptography, the Rabin Signature Scheme is covered in most introductory courses on cryptography. The Rabin Signature Scheme is existentially unforgeable in the random oracle model assuming the integer factorization problem is intractable. The Rabin Signature Scheme is also closely related to the Rabin cryptosystem. ==Original Algorithm== The algorithm relies on a collision-resistant hash function *Key Generation * *The signer ''S'' chooses primes ''p'',''q'' each of size approximately ''k/2'' bits, and computes the product * *''S'' then chooses a random ''b'' in . * *The public key is ''(n,b)'' * *The private key is ''(p,q)'' *Signing * *To sign a message ''m'' the signer ''S'' picks random padding ''U'' and calculates ''H(mU)'' * *''S'' then solves * *If there is no solution ''S'' picks a new pad ''U'' and tries again. If ''H'' is truly random the expected number of tries is 4. * *The signature on ''m'' is the pair ''(U,x)'' *Verification * *Given a message ''m'' and a signature ''(U,x)'' the verifier ''V'' calculates ''x(x+b)'' and ''H(mU)'' and verifies that they are equal 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Rabin signature algorithm」の詳細全文を読む スポンサード リンク
|